package com.lei.backtrcking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: leiGer
 * @Date: 2021/06/29
 * @Time: 23:06
 */

/**
 * 回溯法解决组合问题，
 *给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 */
public class LeetCode77 {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    LinkedList<Integer> path = new LinkedList<>();
    private void backtrcking(int n,int k,int startIndex){
        //向下递归停止条件
        if(path.size() == k){
            res.add(new ArrayList<Integer>(path));
            return;
        }
        //剪枝操作： n - (k-path.size()) + 1
        /**
        *  1、 已经选择的元素个数：path.size();

        *  2、 还需要的元素个数为: k - path.size();

        *  3、 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

        *   为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
        */
        for (int i = startIndex;i <= n - (k-path.size()) + 1;i++){
            path.add(i);
            backtrcking(n,k,i+1);
            path.removeLast();
        }
    }

    public List<List<Integer>> combine(int n,int k){
        backtrcking(n,k,1);
        return res;
    }

    public static void main(String[] args) {
        int n = 4,k = 2;
        LeetCode77 leetCode77 = new LeetCode77();
        List<List<Integer>> res = leetCode77.combine(n, k);
        System.out.println(Arrays.asList(res));
    }

}
